
#include "fieldgenerator.h"
#include "Bot.h"
#include "Logger.h"
#include <math.h>
#include <functional>
#include <map>
#include <queue>
#include <cfloat>
#include <cassert>
#include <algorithm>
#include <stdint.h>

using namespace std;

//constructor
Bot::Bot():field(state)
{

};

//plays a single game of Ants.
void Bot::playGame()
{
    //reads the game parameters and sets up
    Logger::theLogger() << "Reading initial state" << endl;
    cin >> state;
    state.setup();
    endTurn();
    field.initField();
    Logger::theLogger() << "Turn 0 completed" << endl;

    //continues making moves while the game is not over
    while(cin >> state)
    {
	Logger::theLogger() << "Starting updateVision" << endl;
        state.updateVisionInformation();
	Logger::theLogger() << "Finished updateVision" << endl;
	Logger::theLogger() << "Start clearCaches" << endl;
	field.clearCaches();
	Logger::theLogger() << "Finished clearCaches" << endl;
	Logger::theLogger() << "Starting analyzeMap" << endl;
	state.analyzeMap();
	Logger::theLogger() << "Finished analyzeMap" << endl;
	Logger::theLogger() << "Starting buildSquads" << endl;
	buildSquads();
	Logger::theLogger() << "Finished buildSquads" << endl;
	Logger::theLogger() << "Starting makeMoves" << endl;
        makeMoves();
	Logger::theLogger() << "Finished makeMoves" << endl;
        endTurn();
    }
};

void Bot::printSquad(const int& squad_id)  {
    Logger::theLogger() << " squad_id:" << squad_id << ",squad_size:" 
			<< squadList[squad_id].size() << endl;
    Logger::theLogger() << "Ant List:" ;
	    
    for(vector<Location>::const_iterator it = squadList[squad_id].begin();
	it!=squadList[squad_id].end();it++) {
	Logger::theLogger() << "(" << it->row << "," << it->col << "," << state.grid[it->row][it->col].ant << ")" <<  endl;
    }
}

// go through list of ants and group nearby ants in squads
// A squad can be a single ant or upto 10 ants. Each squad
// is scheduled as a unit and moved as unit.
void Bot::buildSquads() {
    clearSquads();
    processedAnts.clear();
    int squad_id =0;
    int SQUAD_SIZE=9999;
    int num_real_squads = 0;
    for (int i=0;i<state.ants.size();i++) {
	if (isInSquad(state.ants[i])) 
	    continue;//skip any ants that are already in squad	
	squad_id++;
	squadList[squad_id].push_back(state.ants[i]);
	inSquad[state.ants[i]] = true;
	std::vector<Location> enemyAntList,enemyHillList;
	state.findEnemyAntsInRadius(state.ants[i],state.viewradius,enemyAntList);
	state.findEnemyHillsInRadius(state.ants[i],state.viewradius,enemyHillList);
	if (enemyAntList.size()==0 && enemyHillList.size()==0) {
	    continue;
	}
	std::vector<Location> antList;
	state.findFriendlyAntsInRadius(state.ants[i],state.attackradius*2,antList);
	bool squad_created =false;
	for(std::vector<Location>::iterator it = antList.begin();
	    it!=antList.end();it++){

	    if (isInSquad(*it)) 
		continue;
	    
	    if (squadList[squad_id].size()<SQUAD_SIZE) {
		squadList[squad_id].push_back(*it);
		inSquad[*it] = true;
		squad_created = true;
	    }
	    else {
		break; //this squad is full.
	    }
	}
	if (squad_created)
	    num_real_squads++;
    }
    Logger::theLogger() << "Final number of real squads" << num_real_squads << endl;
}

bool Bot::isInSquad(const Location& loc) const  {
    if (inSquad.find(loc)!=inSquad.end()) 
	return true;
    return false;
}

void Bot::clearSquads() {
    inSquad.clear();
    squadList.clear();
}

bool Bot::findNearbyValidLoc(const Location& loc,Location& validLoc) {
    for (int i=0;i<4;i++) {
	Location nLoc=state.getLocation(loc,i);
	if ((!state.grid[nLoc.row][nLoc.col].isWater) &&
	    (state.grid[nLoc.row][nLoc.col].ant<0)) {
	    validLoc = nLoc;
	    return true;
	}
    }
    return false;
}

bool Bot::squadDefendHill(const int& squad_id) {
    for (int i=0;i<squadList[squad_id].size();i++) {
	Location hillLoc;
	if (state.myHillInView(squadList[squad_id][i],state.viewradius/2,hillLoc)) {
	    stack<int> myPath;
	    int numNodes;
	    int myPathLen=LARGEVAL;
	    if (state.findPath(hillLoc,squadList[squad_id][i],myPath,numNodes)) {
		myPathLen=myPath.size();
	    }
	    vector<Location> enemyAnts;
	    state.findEnemyAntsInRadius(hillLoc,state.viewradius,enemyAnts);
	    if (enemyAnts.size()>0) {
		int shortestPathLen;
		int enemyPathLen=LARGEVAL;
		Location enemyAnt;
		for(int i=0;i<enemyAnts.size();i++) {
		    stack<int> enemyPath;
		    if (state.findPath(hillLoc,enemyAnts[i],enemyPath,numNodes)) {
			if (enemyPath.size()<enemyPathLen) {
			    enemyPathLen=enemyPath.size();
                            enemyAnt = enemyAnts[i];
			}
		    }
		}
                if (enemyPathLen==LARGEVAL)
                    return false;
		Location moveToLoc,validLoc;
		if (myPathLen<enemyPathLen) {
                    moveToLoc=enemyAnt;
                }else {
                    moveToLoc = hillLoc;
                    if (findNearbyValidLoc(hillLoc,validLoc)) {
                        moveToLoc = validLoc;
                    }
                }

		if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),moveToLoc,shortestPathLen)) {
		    return true;
		}
		else 
		    return false;
	    }
	}
    }
    return false;
}

void Bot::moveSquad(const int& squad_id) {
    Timer t;
    t.start();
    Logger::theLogger() <<endl <<  "Moving Squad_id: " << squad_id << ", squad_size: " << squadList[squad_id].size() << endl;
    printSquad(squad_id);
    if (!squadDefendHill(squad_id)) {
	Logger::theLogger() << endl << "Squad Defend Hill finished at :" << t.getTime() << "ms" << endl;
	if (!squadHuntHill(squad_id)) {
	    Logger::theLogger() << "Squad Hunt Hill finished at:" << t.getTime() << "ms"<< endl;
	    if (!squadHuntFood2(squad_id)) {
		Logger::theLogger() << "Squad Hunt Food finished at:" << t.getTime() << "ms" << endl;
		if (!squadHuntAnt(squad_id)) {
		    Logger::theLogger() << "Squad Hunt Ant finished at:" << t.getTime() << "ms" << endl;  
                    squadMakeExplorers(squad_id);
                    // if (!moveToFrontLineHistoryBased(squad_id)) {
                    //     Logger::theLogger() << "moveToFrontLineHistoryBased  finished at:" << t.getTime() << "ms" << endl;  
                    //     solveMap(squad_id);
                    //     Logger::theLogger() << "solveMap finished at:" << t.getTime() << "ms" << endl;  
                    // }
		}
	    }
	}
    }
    Logger::theLogger() << "Finished Moving Squad_id: " << squad_id << ", squad_size: " << squadList[squad_id].size() << endl;
    Logger::theLogger() << "Squad Move took:" << t.getTime() << "ms" << endl;
}

//returns a list of paths for each ant in squad to loc
PathQueue Bot::generateSquadMoves(vector<Location>::iterator start,
				  vector<Location>::iterator end,
				  const Location& loc) {
    PathQueue pq;
    for (vector<Location>::iterator it = start; it!=end;it++ ) {
	stack<int> path;
	int numNodesExplored = 0;
	state.findPath(*it,loc,path,numNodesExplored);
	if (path.empty()) {
	    Logger::theLogger() << "Could not find path for "<< *it << " to " << loc 
				<< " numNodesExplored:" << numNodesExplored <<endl;
	}
	else {
	    Logger::theLogger() << "found path for " << *it << " to " << loc
				<< " numNodesExplored:" << numNodesExplored << endl;
	}
	pq.push(PathQueueEntry(*it,path));
    }
    return pq;
}

bool Bot::moveSquadTo(const vector<Location>::iterator& start,
		      const vector<Location>::iterator& end,
		      const Location& loc,int& shortestPathLen) {
    Logger::theLogger() <<"Moving Squad to : " << loc.row << "," << loc.col << endl;
    //generate all paths for units in squad
    PathQueue squadMoves = generateSquadMoves(start,end,loc);
    PathQueue squadMoveCopy;
    stack< pair <PathQueueEntry,int> > moveStack;
    stack<pair <Location, PathQueueEntry> > battleLocations;
    vector<Location> losingAnts;
    while (!squadMoves.empty()) {
	//get the ant and path and make the move
	PathQueueEntry antPath = squadMoves.top();
	squadMoves.pop();
	if (antPath.path.empty() ) {
	    Logger::theLogger() << "Path is empty for squad member:" << antPath.antLoc << endl;
	    continue;
	}
	Location nLoc = state.getLocation(antPath.antLoc,antPath.path.top());
	Logger::theLogger() << "Attempting Next Move for Squad:" << nLoc << endl;
	int saveAnt = state.mockMakeMove(antPath.antLoc,antPath.path.top());
	moveStack.push(pair<PathQueueEntry,int>(antPath,saveAnt));
	battleLocations.push(pair<Location, PathQueueEntry>(nLoc,antPath));
    }
    int battleResult = 0; // we are neutral about this move in general
    while (!battleLocations.empty()) {
	int localBattleResult = resolveBattleSimple(battleLocations.top().first,FOCUS_BASED) ;
	Logger::theLogger() << "Local BattleResult is:" << localBattleResult << endl;
 	if (localBattleResult>0) {
	    squadMoveCopy.push(battleLocations.top().second);
 	}
	else if (localBattleResult==0) { 
	    bool has_food=false;
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = state.getLocation(battleLocations.top().first,d);
		if (state.grid[nLoc.row][nLoc.col].isFood ||
		    state.grid[nLoc.row][nLoc.col].isHill) {
		    squadMoveCopy.push(battleLocations.top().second);
		    has_food=true;
		    break;
		}

	    }
	    if (!has_food) {
		losingAnts.push_back(battleLocations.top().second.antLoc);
	    }    
	}
	else {
	    losingAnts.push_back(battleLocations.top().second.antLoc);
	}
	battleResult +=localBattleResult;
	battleLocations.pop();
    }
    while (!moveStack.empty()) {
	pair<PathQueueEntry,int> moveEntry = moveStack.top();
	PathQueueEntry antPath = moveEntry.first;
	moveStack.pop();
	state.unmakeMockMove(antPath.antLoc,antPath.path.top(),moveEntry.second);
    }
    Logger::theLogger() << "Final BattleResult is:" << battleResult << endl;

    if (!squadMoveCopy.empty()) {
	//now make all these moves
	bool first = true;
	bool didmovesquad = false;
	while (!squadMoveCopy.empty()) {
	//get the ant and path and make the move
	    PathQueueEntry antPath = squadMoveCopy.top();
	    if (first) {
		shortestPathLen = antPath.path.size();
		first = false;
	    }
	    else if (shortestPathLen>antPath.path.size())  {
		    shortestPathLen = antPath.path.size();
	    }
	    squadMoveCopy.pop();
	    Location nLoc = state.getLocation(antPath.antLoc,antPath.path.top());

	    if (state.grid[nLoc.row][nLoc.col].ant!=0) {
		//save destinations for ants
		state.makeMove(antPath.antLoc,antPath.path.top());
		didmovesquad =true;
	    }
	    else {
		Logger::theLogger() << " way blocked for ant: " << antPath.antLoc << ",nextLoc:" << nLoc << endl;
	    }
	}
    
	//make sure these losing ants are safe in current locations otherwise move them
	for(int i=0;i<losingAnts.size();i++) {
	    tryEscape(losingAnts[i]);
	}
	return didmovesquad;
    }
    //make sure these losing ants are safe in current locations otherwise move them
    for(int i=0;i<losingAnts.size();i++) {
	tryEscape(losingAnts[i]);
    }
    return false;
}

bool Bot::squadPotentialBasedMove(const int& squad_id) {
    int direction;    
    for(vector<Location>::iterator it = squadList[squad_id].begin();
	it!=squadList[squad_id].end();it++) {
	Location ant = *(it);
	if (field.higher(ant,direction)) {
	    Location nLoc = state.getLocation(ant,direction);
	    if (state.grid[nLoc.row][nLoc.col].ant!=0) {
		Logger::theLogger() << "PotentialBasedMove: ";
		Logger::theLogger() << "o " << ant.row << " " << ant.col << " " << CDIRECTIONS[direction] << endl;
		state.makeMove(ant,direction);
		field.visited(ant);
	    }
	}
    }
    return true;
}

bool Bot::shouldAttack() const{
    return true;
    if (state.knownLandPercent<0.5) {
	return false;
    }
    //compute number of ants we control vs number of visible enemies
    double antRatio = (double)state.ants.size()/state.enemies.size();
    if (antRatio < 1.2) 
	return false;
    return true;
}

bool Bot::squadHuntHill(const int& squad_id) {
//Try to find a closest ant and move towards it.
    Location antLoc = *(squadList[squad_id].begin());
    Location enemyHillLoc;
    stack<int> path;
    int numNodesExplored=0;
    Logger::theLogger() << "Hunting hills " << endl;
    if (state.findClosestEnemyHill2(antLoc,enemyHillLoc,path,numNodesExplored)) {
	Logger::theLogger() << "Ant at: " << antLoc.row << "," <<antLoc.col << endl;
	Logger::theLogger() << "Found enemyHill: " << enemyHillLoc.row << "," << enemyHillLoc.col << endl;
	Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	if (!path.empty()) {
	    Location nLoc = state.getLocation(antLoc,path.top());
	    if (state.grid[nLoc.row][nLoc.col].ant!=0) {
		int shortestPathLen;
		if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),enemyHillLoc,shortestPathLen)) {
		    state.grid[enemyHillLoc.row][enemyHillLoc.col].tracking+=1;
		    return true;
		}
		else
		    return false;
	    }
	    else {
		Logger::theLogger() <<"Ant already next to enemy or way is blocked" << endl;
		if (nLoc==enemyHillLoc) 
		    return true;
	    }
	}
    }
    return false;
}

bool Bot::squadHuntAnt(const int& squad_id) {
    if (!shouldAttack())  {
	return false;
    }
//Try to find a closest ant and move towards it.
    Location antLoc = *(squadList[squad_id].begin());
    Location enemyAntLoc;
    stack<int> path;
    int numNodesExplored=0;
    Logger::theLogger() << "Hunting Ants " << endl;
    if (state.findClosestEnemyAnt(antLoc,enemyAntLoc,path,numNodesExplored)) {
	Logger::theLogger() << "Ant at: " << antLoc.row << "," <<antLoc.col << endl;
	Logger::theLogger() << "Found enemyAnt: " << enemyAntLoc.row << "," << enemyAntLoc.col << endl;
	Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	if (!path.empty()) {
	    Location nLoc = state.getLocation(antLoc,path.top());
	    if (nLoc!=enemyAntLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
		int shortestPathLen;
		if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),enemyAntLoc,shortestPathLen)) {
		    state.grid[enemyAntLoc.row][enemyAntLoc.col].tracking+=1;
		    return true;
		}
		else
		    return false;
	    }
	    else {
		Logger::theLogger() <<"Ant already next to enemy or way is blocked" << endl;
		if (nLoc==enemyAntLoc) 
		    return true;
	    }
	}
    }
    return false;
}

bool Bot::squadHuntFood2(const int& squad_id) {
    Location closestFoodLoc;
    int shortest_path = LARGEVAL;
    for (int i=0;i<squadList[squad_id].size() ;i++) {
	Location ant = squadList[squad_id][i];
	Location foodLoc;
	stack<int> path;
	int numNodesExplored = 0;
	if (state.findClosestFood(ant,foodLoc,path,numNodesExplored)) {
	    if (!path.empty()) {
		if (path.size() < shortest_path) {
		    closestFoodLoc = foodLoc;
		    shortest_path = path.size();
		}
	    }
	}
    }
    if (shortest_path==LARGEVAL) {
	return false;
    }
    Logger::theLogger() << "Found food: " << closestFoodLoc.row << "," << closestFoodLoc.col << endl;

    //closestFoodLoc now contains the closest food to some ant in the squad.
    //shortest_path contains the size of shortest path from some ant in the squad
    //to the food.
    int enemyPathLength = LARGEVAL;
    Location enemyAntLoc;
    stack<int> enemyAntPath;
    int numNodesExplored2;
    if (state.findClosestEnemyAnt(closestFoodLoc,enemyAntLoc,enemyAntPath,numNodesExplored2)) {
	if (enemyAntPath.size() < shortest_path) {
	    Logger::theLogger() << "Enemy has shorter path to food than me avoid food" << endl;
	    return false;
	}
    }
    Logger::theLogger() << "enemyAnt find success" << endl;
    //Is there another squad that has a shorter path than this squad to this food?
    if (state.grid[closestFoodLoc.row][closestFoodLoc.col].tracking>0) {
	int maxPathLength = state.foodTrackingPathLengths[closestFoodLoc];
	if (maxPathLength>shortest_path) {
	    int shortestPathLen;
	    if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),closestFoodLoc,shortestPathLen)) {
		state.grid[closestFoodLoc.row][closestFoodLoc.col].tracking+=1;
		state.foodTrackingPathLengths[closestFoodLoc] = shortestPathLen;
		return true;
	    }
	    else 
		return false;
	}
	else {
	    Logger::theLogger() << "food is already being tracked skipping" << endl;
	    return false;
	}
    }
    else { //no other squad is tracking this food
	Logger::theLogger() << "food is not being tracked move squad to food" << endl;
	int shortestPathLen;
	if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),closestFoodLoc,shortestPathLen)) {
	    state.grid[closestFoodLoc.row][closestFoodLoc.col].tracking+=1;
	    state.foodTrackingPathLengths[closestFoodLoc] = shortestPathLen;
	    return true;
	}
	return false;
    }
}

bool Bot::squadHuntFood(const int& squad_id) {
    //The first ant in the squad is the leader.
    Location leaderAnt = *(squadList[squad_id].begin());
    Location foodLoc;
    stack<int> path;
    int numNodesExplored = 0;
    if (state.findClosestFood(leaderAnt,foodLoc,path,numNodesExplored)) {
	if (!path.empty()) {
	    Logger::theLogger() << "Squad at: " << leaderAnt.row << "," <<leaderAnt.col << endl;
	    Logger::theLogger() << "Found food: " << foodLoc.row << "," << foodLoc.col << endl;
	    Logger::theLogger() << "numNodesExplored:" << numNodesExplored << endl;
	    int enemyPathLength = 2<<31;
	    Location enemyAntLoc;
	    stack<int> enemyAntPath;
	    int numNodesExplored2;
	    if (state.findClosestEnemyAnt(foodLoc,enemyAntLoc,enemyAntPath,numNodesExplored2)) {
		if (enemyAntPath.size() < path.size()) {
		    Logger::theLogger() << "Enemy has shorter path to food than me avoid food" << endl;
		    return false;
		}
	    }
	    if (state.grid[foodLoc.row][foodLoc.col].tracking>0) {
		int maxPathLength = state.foodTrackingPathLengths[foodLoc];
		if (maxPathLength > path.size()) {
		    Location nLoc = state.getLocation(leaderAnt,path.top());
		    if (nLoc!=foodLoc && state.grid[nLoc.row][nLoc.col].ant!=0) {
			int shortestPathLen;
			if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),foodLoc,shortestPathLen)) {
			    state.grid[foodLoc.row][foodLoc.col].tracking+=1;
			    state.foodTrackingPathLengths[foodLoc] = shortestPathLen;
			    return true;
			}
			else
			    return false;
		    }
		}
		else {
		    Logger::theLogger() << "food is already being tracked skipping" << endl;
		    return false;
		}
	    }
	    else { //no other squad is tracking this food
		Logger::theLogger() << "food is not being tracked move squad to food" << endl;
		Location nLoc = state.getLocation(leaderAnt,path.top());
		if (nLoc!=foodLoc) {
		    int shortestPathLen;
		    if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),foodLoc,shortestPathLen)) {
			state.grid[foodLoc.row][foodLoc.col].tracking+=1;
			state.foodTrackingPathLengths[foodLoc] = shortestPathLen;
			return true;
		    }
		}
		else {
		    Logger::theLogger()  << "already next to food or way blocked by an ant, not moving" << endl;
		    if (nLoc==foodLoc) 
			return true;
		}
	    }
	}
    }
    return false;
}

void Bot::safeMakeMove(const Location& ant,int direction) {
    Location nLoc = state.getLocation(ant,direction);
    if ((state.grid[nLoc.row][nLoc.col].ant<0) &&
	(!state.grid[nLoc.row][nLoc.col].isWater)) {
	state.makeMove(ant,direction);
	state.antWalkMap[nLoc] = state.antWalkMap[ant];
	state.antWalkMap.erase(ant);
    }
    else {
	Logger::theLogger() << "safeMakeMove, move would kill an ant " << ant << ":" << CDIRECTIONS[direction] << endl;
    }
}

//Use Pledge algorithm to solve the map
void Bot::antSolveMap(const Location& ant) {
    Logger::theLogger() << "antWalkMap.turns is :" << state.antWalkMap[ant].turns << endl;
    if (!state.antWalkMap[ant].following) {
	Logger::theLogger() << "ant is not following try moving in normal direction" << endl;
	Location nLoc = state.getLocation(ant,state.antWalkMap[ant].d);
	int moveDirection = state.antWalkMap[ant].d;
	int turnCnt = 0;
	while (state.grid[nLoc.row][nLoc.col].isWater ||
	       (state.grid[nLoc.row][nLoc.col].ant>=0) ) {
	    turnCnt++;
	    if (turnCnt>4) 
		break;
	    Logger::theLogger() << "ant is blocked try a turn" << endl;
	    //start following
	    state.antWalkMap[ant].following=true;
	    //try turning right if you can't then try a left
	    state.antWalkMap[ant].followd = (state.antWalkMap[ant].followd+1)%4;
	    state.antWalkMap[ant].turns+=1;
	    nLoc = state.getLocation(ant,state.antWalkMap[ant].followd);
	    moveDirection = state.antWalkMap[ant].followd;
	}
	safeMakeMove(ant,moveDirection);
    }
    else {
	Logger::theLogger() << "ant is following a wall" << endl;
	//we need to keep our left hand on the wall 
	int left = ((state.antWalkMap[ant].followd-1)<0)?3:state.antWalkMap[ant].followd-1;
	Location leftLoc = state.getLocation(ant,left);
	if (!state.grid[leftLoc.row][leftLoc.col].isWater) {
	    Logger::theLogger() << "ant lost the wall turning left" << endl;
	    //we lost the wall turn left.
	    state.antWalkMap[ant].followd = left;
	    state.antWalkMap[ant].turns-=1;
	    if ((state.antWalkMap[ant].turns==0) && (state.antWalkMap[ant].followd==state.antWalkMap[ant].d)) {
		Logger::theLogger() << "turns is zero stop following" << endl;
		//stop following
		state.antWalkMap[ant].following=false;
		state.antWalkMap[ant].followd=state.antWalkMap[ant].d;
	    }
	    safeMakeMove(ant,state.antWalkMap[ant].followd);
	}
	else {
	    Logger::theLogger() << "still following the wall move in follow direction" << endl;
	    //we move in followd if not possible make a right turn
	    Location followLoc = state.getLocation(ant,state.antWalkMap[ant].followd);
	    if (!state.grid[followLoc.row][followLoc.col].isWater &&
		(state.grid[followLoc.row][followLoc.col].ant<0)) {
		Logger::theLogger() << "followDirection is open so going forward" << endl;
		//we are not blocked and still following a wall so move in this direction
		safeMakeMove(ant,state.antWalkMap[ant].followd);
	    }
	    else {
		Logger::theLogger() << "followDirection is blocked, make a right turn" << endl;
		//we are blocked make a right turn
		int turnCnt=0;
		while (state.grid[followLoc.row][followLoc.col].isWater ||
		       (state.grid[followLoc.row][followLoc.col].ant>=0)) {
		    turnCnt++;
		    if (turnCnt>4) 
			break;
		    Logger::theLogger() << "followDirection blocked, making turn" << endl;
		    state.antWalkMap[ant].followd = (state.antWalkMap[ant].followd+1)%4;
		    state.antWalkMap[ant].turns+=1;
		    followLoc = state.getLocation(ant,state.antWalkMap[ant].followd);
		}
		safeMakeMove(ant,state.antWalkMap[ant].followd);
	    }
	}
    }
}

void Bot::solveMap(const int& squad_id) {
    for(int i=0;i<squadList[squad_id].size();i++) {
	Location ant  = squadList[squad_id][i];
	bool nomove=false;
	int moveDirection=-1;

	if (state.antWalkMap.find(ant) ==state.antWalkMap.end()) {
	    //ant is not in maze walk map so insert it
	    State::AntWalkDetails antWalkDetails;
	    antWalkDetails.d = rand()%4;
	    antWalkDetails.turns = 0;
	    antWalkDetails.following=false;
	    antWalkDetails.followd = antWalkDetails.d;
	    state.antWalkMap[ant] = antWalkDetails;
	}
	antSolveMap(ant);
    }
}

void Bot::antMakeExplorer(const Location& loc) {
    explorers.push_back(loc);
}

void Bot::squadMakeExplorers(const int& squad_id) {
    for(int i=0;i<squadList[squad_id].size();i++) {
	Location ant  = squadList[squad_id][i];
        antMakeExplorer(ant);
    }
}

void Bot::multiSourceBFSExplore() {
    map<Location,int > antMoves;
    if (explorers.empty()) {
        Logger::theLogger() << "Explorer list is empty, do nothing" << endl;
        return;
    }
    state.multiSourceBFSFindMove(explorers,antMoves);
    for (map<Location,int >::iterator it= antMoves.begin();
         it!= antMoves.end();it++) {
        Logger::theLogger() <<"Processing Explorer ant :" << it->first << endl;
        safeMakeMove(it->first,it->second);
    }
}

struct frontLineOrder {
    int priority;
    int direction;
    
    frontLineOrder():priority(0),direction(0) {};
    frontLineOrder(int p,int d):priority(p),direction(d) {
    }
    bool operator <(const frontLineOrder& other)  const{
	return priority>other.priority;
    }
};

bool Bot::moveToFrontLineHistoryBased(const int& squad_id) {
    //for each ant generate the 4 directions and pick the one that
    //hasn't been visited in the longest time.
    vector<int> directionVector;
    for (int d=0;d<TDIRECTIONS;d++) {
	directionVector.push_back(d);
    }
    for(int i=0;i<squadList[squad_id].size();i++) {
	int oldestMove = LARGEVAL;
	int oldestTurn = LARGEVAL;
	Location ant  = squadList[squad_id][i];
        if ((state.antWalkMap.find(ant)!=state.antWalkMap.end()) &&
            (state.antWalkMap[ant].following)){
            Logger::theLogger() << "Ant is in follow mode do not reroute" << endl;
            continue;
        }

        vector<int> moveList;
	random_shuffle(directionVector.begin(),directionVector.end());
	priority_queue< frontLineOrder > moveOrder;
	for (vector<int>::iterator it=directionVector.begin();it!=directionVector.end();it++) {
	    int d = *it;
	    Location nLoc = state.getLocation(ant,d);
	    if (state.grid[nLoc.row][nLoc.col].ant>=0 ||
		state.grid[nLoc.row][nLoc.col].isWater||
		state.grid[nLoc.row][nLoc.col].isFood ||
		state.grid[nLoc.row][nLoc.col].isHill
		) 
	      continue;
	    moveOrder.push(frontLineOrder(state.visitedHistory[nLoc.row][nLoc.col],d));
	}
	int max_vision=0;
	frontLineOrder finalMove;
	frontLineOrder anywayMove;
	Location anywayLoc;
	bool found_move = false;
	while (!moveOrder.empty()) {
	    Logger::theLogger() << "looping to find final movetoFrontline move" << endl;
	    frontLineOrder moveToMake = moveOrder.top();
	    moveOrder.pop();
	    int savedAnt = state.mockMakeMove(ant,moveToMake.direction);
	    Location nLoc = state.getLocation(ant,moveToMake.direction);
	    int battleResult = resolveBattleSimple(nLoc,FOCUS_BASED);
	    state.unmakeMockMove(ant,moveToMake.direction,savedAnt);
	    int visionIncrease = state.increasesVision(nLoc);
	    //if we are just stuck near hill move anyway
	    if (battleResult>0 && visionIncrease && (visionIncrease>max_vision)) {
		finalMove = moveToMake;
		max_vision = visionIncrease;
		found_move=true;
	    }
	}
	if (found_move) {
	    state.makeMove(ant,finalMove.direction);
	    return true;
	}
    }
    return false;
}

void Bot::moveToFrontLine(const int& squad_id) {
    Logger::theLogger() << "Moving To FrontLine" << endl;
    if (state.frontLine.empty()) {
	Logger::theLogger() <<"Frontline is empty" << endl;
	return;
    }
    Logger::theLogger() << "Frontline Size is " << state.frontLine.size() << endl;

    double min_dist =DBL_MAX;
    Location frontLoc =squadList[squad_id][0];
    Timer t;
    t.start();
    if (state.antDestinationMap.find(squadList[squad_id][0])!=state.antDestinationMap.end()){
	//This squad already has a destination just move them along
	Location destination=state.antDestinationMap[squadList[squad_id][0]];
	Logger::theLogger() << "squad_id:" << squad_id  << " has a destination " << destination.row << "," << destination.col << endl;

	int shortestPathLen;   
	//remove current entry, moveSquadTo will enter a new one for this ant
	state.antDestinationMap.erase(squadList[squad_id][0]);
	if (destination!=squadList[squad_id][0]) {
	    if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),destination,shortestPathLen)) {
		state.grid[destination.row][destination.col].tracking +=1;
		return;
	    }
	}
	return; //return anyway even if we can't proceed.
    }
    Logger::theLogger() << "Start searching for frontLine location at: "<< t.getTime() <<"ms" << endl; 
    int moveAttempts = 0;
    
    while (moveAttempts<5) {
	frontLoc = state.frontLine[rand()%state.frontLine.size()];
	if (state.grid[frontLoc.row][frontLoc.col].tracking>1 )  {
	    moveAttempts+=1;
	    continue;
	}
	if (moveAttempts>4) {
	    Logger::theLogger()  << "Tried 10 different frontLine locations didn't find a path stop searching" << endl;
	    int battleResult = resolveBattleSimple(squadList[squad_id][0],FOCUS_BASED);
	    if (battleResult<0) 
	      tryEscape(squadList[squad_id][0]);
	    break;
	}
	if (frontLoc == squadList[squad_id][0])  {
	    Logger::theLogger() << "Frontline loc " << frontLoc << " is same as squad leader location" << squadList[squad_id][0] << endl;
	    return;
	}
	int shortestPathLen;
	if (moveSquadTo(squadList[squad_id].begin(),squadList[squad_id].end(),frontLoc,shortestPathLen)) {
	    for(std::vector<Location>::iterator it=squadList[squad_id].begin();
		it!=squadList[squad_id].end();it++){
			    state.antDestinationMap[*it] = frontLoc;
	    }
	    state.grid[frontLoc.row][frontLoc.col].tracking+=1;
	    break;
	}
	moveAttempts++;
    }
    Logger::theLogger() << "Finished searching for frontLine location at: "<< t.getTime() <<"ms" << " , moveAttempts:" << moveAttempts << endl;     
}

void Bot::tryEscape(const Location& loc) {
    Logger::theLogger() << "Starting Escape search for ant at Location:" << loc << endl;
    for(int d=0; d<TDIRECTIONS; d++)
    {
	Location nLoc = state.getLocation(loc, d);
	if (state.grid[nLoc.row][nLoc.col].ant>=0 ||
	    state.grid[nLoc.row][nLoc.col].isWater||
	    state.grid[nLoc.row][nLoc.col].isFood ||
	    state.grid[nLoc.row][nLoc.col].isHill ) 
	    continue;

	int battleResult = resolveBattleSimple(nLoc,FOCUS_BASED);
	if (battleResult>0) {
	    Logger::theLogger() << "Ant at " << loc << " escaping to " << nLoc << endl;
	    state.makeMove(loc,d);
	    return;
	}
    }
    Logger::theLogger()  << " Ant at " << loc << " has no escape route " << endl;
}

bool Bot::isFoodAdjacent(const Location& loc) {
    for(int d=0; d<TDIRECTIONS; d++)
    {
	Location nLoc = state.getLocation(loc, d);
	if (state.grid[nLoc.row][nLoc.col].isFood)
	    return true;
    }
    return false;
}

int Bot::resolveBattleSimple(const Location& nLoc,BATTLEMETHOD battleMethod) {
    if (battleMethod==DMG_BASED) {
	return resolveBattleDmgBased(nLoc);
    }
    else if (battleMethod==FOCUS_BASED) {
	return resolveBattleFocusBased(nLoc);
    }
    else {
	//default to focus based
	return resolveBattleFocusBased(nLoc);
    }
}

int Bot::resolveBattleFocusBased(const Location& nLoc) {
    Timer t;
    t.start();
    Location ant = nLoc;
    vector<Location> enemyAnts;
    //Find and move each enemy ant one step closer to nLoc
    Logger::theLogger() << "Start First Ant Query at:" << t.getTime() << "ms" << endl;
    state.findEnemyAntsInRadius(nLoc,state.attackradius+2,enemyAnts);    
    Logger::theLogger() <<"End First Ant Query" << t.getTime() << "ms"<< endl;
    stack< pair <pair<Location,stack<int> > ,int> > moveStack;
    /*    if (enemyAnts.size() >0) {
	for (int i=0;i<enemyAnts.size();i++) {
	    stack<int> path;
	    int numNodesExplored;
	    state.findPath(enemyAnts[i],nLoc,path,numNodesExplored);
	    if (path.empty()) 
		continue;
	    Logger::theLogger() << "Moving enemy ant at " << enemyAnts[i] << " due " << CDIRECTIONS[path.top()] << endl;
	    int saveAnt = state.mockMakeMove(enemyAnts[i],path.top());
	    moveStack.push(pair <pair< Location,stack<int> >,int > (pair<Location,stack<int> > (enemyAnts[i],path),saveAnt));
	}
        }*/

    //Now resolve the battles with correct radius
    enemyAnts.clear();
    Logger::theLogger() << "Start Second Ant Query" << t.getTime() << "ms"<< endl;
    state.findEnemyAntsInRadius(nLoc,state.attackradius,enemyAnts);    
    Logger::theLogger() <<"End Second Ant Query" << t.getTime() << "ms"<< endl;

    int battleResult = 1; //victory by default
    if (enemyAnts.size() >0) {
	for (int i=0;i<enemyAnts.size(); i++) {
	    vector<Location> thisAntsEnemyList;
	    Logger::theLogger() << "Start Third Ant Query "<< t.getTime() << "ms" << endl;
	    state.findThisAntsEnemiesInRadius(enemyAnts[i],state.attackradius,thisAntsEnemyList,
					      state.grid[enemyAnts[i].row][enemyAnts[i].col].ant);
	    Logger::theLogger() << "End Third Ant Query" << t.getTime() << "ms"<< endl;
	    Logger::theLogger() << "enemyAnt :" << enemyAnts[i] << ",enemies:" << thisAntsEnemyList.size() << endl;
	    if (thisAntsEnemyList.size() < enemyAnts.size()) {
		battleResult = -1;
		break;//we found at least one enemy ant which has less enemies than us so break
	    }
	    else if ((thisAntsEnemyList.size()==enemyAnts.size())) { // && (battleResult!=-1)) {
		battleResult = 0;
	    }
	}
    }
    else {
	Logger::theLogger() << " No enemy ants in attack radius of " << nLoc << endl;
    }

    //now undo all the moves
    while (!moveStack.empty()) {
	pair < pair <Location,stack<int> > ,int > move = moveStack.top();
	moveStack.pop();
	state.unmakeMockMove(move.first.first,move.first.second.top(),move.second);
    }
    Logger::theLogger()<< "resolveBattleFocusBased finished at:"<< t.getTime() << "ms" << endl;
    return battleResult;
}

//resolve battle at nLoc. Just find ants that will do dmg to this ant
//and how much dmg each of the friendlies will do to the enemy ants.
// returns 1 if its overall in our favour, 0 if all sides
//lose equal number, -1 if its against us.
int Bot::resolveBattleDmgBased(const Location& nLoc)  {
    //Initialize a battle grid with 0 dmg done to all squares, any squares
    vector< vector<double> > battleGrid(state.rows, vector<double> (state.cols,0));

    Location ant = nLoc;
    vector<Location> enemyAnts,friendlyAnts;
    state.findFriendlyAntsInRadius(nLoc,state.attackradius,friendlyAnts);
    state.findEnemyAntsInRadius(nLoc,state.attackradius*1.5,enemyAnts);
    int nEnemyAnts = enemyAnts.size();
    Logger::theLogger() << "Enemy Ants: " << enemyAnts.size() << endl;
    Logger::theLogger() << "friendly Ants: " << enemyAnts.size() << endl;

    //do battle for all ants not owned by current ant's owner
    //distribute 1 dmg to all the others
    bool did_battle_occur = false;
    if (enemyAnts.size()!=0) {
	did_battle_occur = true;
	double dmg_to_distribute = 1.0/enemyAnts.size();
	Logger::theLogger() << "dmg_to_distribute:" << dmg_to_distribute << endl;
	for(int i=0;i<enemyAnts.size();i++) {
	    battleGrid[enemyAnts[i].row][enemyAnts[i].col]+=dmg_to_distribute;
	}
    }
    if  (friendlyAnts.size()!=0) {
	double dmg_to_distribute = (enemyAnts.size()*1.0/friendlyAnts.size());
	Logger::theLogger() << "dmg_to_distribute:" << dmg_to_distribute << endl;
	for(int i=0;i<friendlyAnts.size();i++) {
	    battleGrid[friendlyAnts[i].row][friendlyAnts[i].col]+=dmg_to_distribute;
	}
    }
    //At this point we should have a battleGrid with all dmg calculations
    //for all ants affected. Now its just a matter of calculating overall
    //ants lost/killed and evaluate if the move is worth it.
    map<int,int> playerAntLosses;
    for(vector<Location>::const_iterator it=friendlyAnts.begin();it!=friendlyAnts.end();it++) {
	Logger::theLogger() << "friendlyAnt at:" << it->row << "," << it->col << endl;
	if (battleGrid[it->row][it->col]>0.9999) {
	    Logger::theLogger() << "dmg to self:" <<battleGrid[it->row][it->col] << endl;
	    playerAntLosses[0] +=1;
	}
    }   

    for(vector<Location>::const_iterator it=enemyAnts.begin();it!=enemyAnts.end();it++) {
	Logger::theLogger() << "enemyAnt at:" << it->row << "," << it->col << endl;
	if (battleGrid[it->row][it->col]>0.9999) {
	    Logger::theLogger() << "dmg to enemy:" <<battleGrid[it->row][it->col] << endl;
	    playerAntLosses[state.grid[it->row][it->col].ant] +=1;
	}
    }   
    int myLosses = playerAntLosses[0] ;
    Logger::theLogger()  << "MyLosses:" << myLosses << endl;
    if ((myLosses==0) && did_battle_occur) {
	return 1;
    }
    else if ((myLosses==0) && !did_battle_occur){
	return 0;
    }
    else {
	int enemyLosses =0 ;
	for(map<int,int>::const_iterator it = playerAntLosses.begin();
	    it!=playerAntLosses.end();it++) {
	    Logger::theLogger() << "player_id: " << it->first << ",losses:" << it->second << endl;
	    if (it->first!=0) {
		enemyLosses+=it->second;
	    }
	}
	Logger::theLogger()<< "enemyLosses:"<< enemyLosses << endl;
	
	if (myLosses>enemyLosses) {
	    if (isFoodAdjacent(nLoc))
		return 1;
	    return -1;
	}
	else if (myLosses==enemyLosses) {
	    if (isFoodAdjacent(nLoc))
		return 1;
	    return 0;
	} else {
	    return 1;
	}	
    }

}


//makes the bots moves for the turn
void Bot::makeMoves()
{
    Logger::theLogger() << "turn " << state.turn << ":" << endl;
    Logger::theLogger() << state << endl;


    //pick out moves per squad
    for (map< int, vector<Location> >::iterator it=squadList.begin();
	 it!=squadList.end();
	 it++) {
	moveSquad(it->first);
    }
    //Finally move all explorers in one sweep
    Logger::theLogger() << "starting multiSourceBFSExploration at " << state.timer.getTime() << "ms" << endl;
    multiSourceBFSExplore();
    Logger::theLogger() << "BFS Exploration took:" << state.timer.getTime() << "ms" << endl;

    Logger::theLogger() << "Move time taken: " << state.timer.getTime() << "ms" << endl << endl;
};

//finishes the turn
void Bot::endTurn()
{
    if(state.turn > 0) {
        state.reset();
        explorers.clear();
    }
    state.turn++;

    cout << "go" << endl;
};
